package 笔试强训;

import java.util.Scanner;

/**
 * @Question 斐波那契凤尾
 * @Date 2022/11/1 15:37
 * @Solution
 */
public class 斐波那契凤尾 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            long n = sc.nextInt();
            if(n==1) {
                System.out.println(1);
                continue;
            } else if(n==2) {
                System.out.println(2);
                continue;
            } else if(n==3) {
                System.out.println(3);
                continue;
            }
            long a = 1;
            long b = 2;
            long c = 3;
            for (int i = 3; i < n; i++) {
                long t = c;
                c = (b + c) % 1000000;
                a = b;
                b = t;
            }
            System.out.println(c);
        }
    }
}
